package com.javaimplementclrs.foundations.getstart;
import java.util.*;
/**
 * Insertion Sort
 * @version 1.00 2013-8-1
 * @author Moking
 */

public class InsertionSort
{
	public static void main(String[] args)
	{
		int[] unsortArr = {7,8,9,10,3,2,6,8,9};
		
		// sort the array
		insertsort(unsortArr);
		System.out.println(Arrays.toString(unsortArr));	    
	}
	
	
	public static int[] insertsort(int[] arr)
	{
		int key = 0;
		for (int j = 1; j < arr.length; j++)
		{
			key = arr[j];
			int i = j - 1;
			while ((i > -1) && (arr[i] > key))
			{
				arr[i + 1] = arr[i];
				i = i - 1;
			}
			arr[i + 1] = key;
		}
		return arr;
	}
}
